package LeetCode刷题.之前的算法;

public class Moorevote {
    //摩尔投票法
    public static void main(String arg[]){
        //找出一堆数字出现次数超过一半的
        int nums[]={1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(searchNumber(nums));
    }
    public static int searchNumber(int nums[]){
//         关键是票数正负数抵消 用于求一堆数中个数超过一半的数字
//        推论一： 若记众数的票数为+1，非众数 的票数为 −1，则一定有所有数字的票数和>0 。
//        推论二： 若数组的前a个数字的票数和=0，则数组剩余(n−a)个数字的 票数和一定仍>0，即后(n−a)个数字的众数仍为x 。
        int x=0;//代表众数
        int vote=0;//票数
        for(int n:nums){
            if(vote==0){//当票数等于0的时候就假设当前的数字为众数
                x=n;
            }
            vote+=(x==n)?1:-1;
        }
        return x;
    }
}
